package net.lab0.wallstreet;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

import javax.xml.datatype.Duration;

import com.google.common.collect.Collections2;
import com.google.common.collect.Lists;

public class AccountingDilemma
{
    public static int pass = 0;
    
    public static List<Integer> solve(int transfer, List<Integer> payments)
    {
        return implementation1starter(transfer, payments);
    }
    
    private static List<Integer> implementation2starter(int transfer, List<Integer> payments)
    {
        Collections.sort(payments);
        return implementation2(transfer, payments, new ArrayList<Integer>(), payments.size());
    }
    
    private static List<Integer> implementation1starter(int transfer, List<Integer> payments)
    {
        // Sorts the list in ascending order
        Collections.sort(payments);
        
        // meta array to know how much we could get by adding all the remaining elements
        int count = payments.size();
        List<Integer> metaArray = new ArrayList<Integer>(count);
        metaArray.add(payments.get(0));
        int sum = 0;
        for (int i = 0; i < count; ++i)
        {
            if (sum <= transfer)
            {
                sum += payments.get(i);
                metaArray.add(sum);
            }
            else
            {
                metaArray.add(i, sum);// avoid overflow
            }
        }
        metaArray = Lists.reverse(metaArray);
        payments = Lists.reverse(payments);
        
        return implementation1(transfer, payments, new ArrayList<Integer>(), 0, metaArray);
    }
    
    /**
     * Same idea as implementation1
     * 
     * @param transfer
     * @param payments
     * @param currentSum
     * @param indexToTest
     * @param metaArray
     * @return
     */
    public static List<Integer> implementation2(int transfer, List<Integer> payments, List<Integer> currentSum,
    int maxIndexToTest)
    {
        int sum = sum(currentSum);
        
        // find the biggest index that could be used to continue the sum
        int Q = transfer - sum;
        int index = Collections.binarySearch(payments.subList(0, maxIndexToTest), Q);
        
        if (index == payments.size() || index == -1)
        {
            return null;
        }
        
        if (index >= 0)
        {
            currentSum.add(payments.get(index));
            return currentSum;
        }
        else
        {
            index = -(index + 1);
            index--; // get the biggest available number that would make the total sum inferior to Q
            currentSum.add(payments.get(index));
        }
        
        // iterate over all the remaining numbers while trying to complement the sum with remaining numbers
        outerLoop: while (sum(currentSum) != transfer)
        {
            // Add to the previous sum the next value that can complement it (T)
            List<Integer> result = implementation2(transfer, payments, currentSum, index);
            // this chain didn't work -> removing the last element and trying with the next biggest value
            if (result == null)
            {
                // not possible to get the list with this element in it -> trying next different value
                int lastValue = currentSum.remove(currentSum.size() - 1);
                int currentValue = lastValue;
                while (currentValue == lastValue)
                {
                    currentValue = payments.get(index);
                    index--;
                    if (index < 0)
                    {
                        break outerLoop;
                    }
                }
                
                currentSum.add(currentValue);
            }
            // hooray !
            else
            {
                return currentSum;
            }
        }
        
        return null;
    }
    
    /**
     * Second try with a better algorithm. This one tries to sum the number starting with the bigger ones and
     * complements the sum that is created this way with smaller values until it reaches the desired value or reached
     * the end of the list. If it reaches the end of the list, it go back 1 iteration and tries with the second biggest
     * number in the list. Etc. until it find a solution or until it tries every meaningful solution.
     * 
     * @param transfer
     *            The bank transfer (Q in the comments)
     * @param payments
     *            The due payments
     * @param currentSum
     *            The current set of values that are tested to find the wanted sum (R+S+T+... in the comments)
     * @param indexToTest
     *            the biggest value for which it makes sense to continue the algorithm
     * @return The list of numbers if there is a solution of <code>null</code> if none.
     */
    public static List<Integer> implementation1(int transfer, List<Integer> payments, List<Integer> currentSum,
    int indexToTest, List<Integer> metaArray)
    {
        int sum = sum(currentSum);
        int testedValue = Integer.MAX_VALUE - sum;
        // TODO: binary search may improve the speed here, as there is no complexity or time requirement I won't try it
        // Tries to build a list with the first number R that is less that or equal to the expected bank transfer Q
        while (sum + testedValue > transfer && indexToTest < payments.size())
        {
            if (metaArray.get(indexToTest) + sum < transfer)
            {
                // this would be impossible
                return null;
            }
            testedValue = payments.get(indexToTest);
            indexToTest++;
        }
        
        if (sum + testedValue == transfer)
        {
            currentSum.add(testedValue);
            return currentSum; // got it !
        }
        
        if (indexToTest == payments.size())
        {
            return null;// sorry. not possible with this combination
        }
        
        // here we are in the case where the sum in not big enough, so we will have to try to add other values
        // Tries to add numbers (S) as big as possible to R to complement it until we get the expected sum -> R + S +
        // ...
        currentSum.add(testedValue);
        /*
         * try for all the remaining values in the list. Possible improvement: stop at the last index for which the sum
         * of the values after it is too small to reach Q.
         */
        while (indexToTest < payments.size())
        {
            // Add to the previous sum the next value that can complement it (T)
            List<Integer> result = implementation1(transfer, payments, currentSum, indexToTest, metaArray);
            // this chain didn't work -> removing the last element and trying with the next biggest value
            if (result == null)
            {
                // not possible to get the list with this element in it -> trying next different value
                int lastValue = currentSum.remove(currentSum.size() - 1);
                int currentValue = lastValue;
                while (indexToTest < payments.size() && currentValue == lastValue)
                {
                    currentValue = payments.get(indexToTest);
                    indexToTest++;
                }
                /*
                 * add unconditionally. If it is different from the last value it's going to work. if it is the same,
                 * it's going to exit the outer loop
                 */
                if (indexToTest < payments.size())
                {
                    currentSum.add(currentValue);
                }
            }
            // hooray !
            else
            {
                return currentSum;
            }
        }
        
        // was not able to find a valid result
        return null;
    }
    
    private static int sum(List<Integer> currentSum)
    {
        int total = 0;
        for (int i : currentSum)
        {
            total += i;
        }
        return total;
    }
    
    /**
     * First try to get the desired list.
     * 
     * @param transfer
     * @param payments
     * @return The list of numbers if there is a solution of <code>null</code> if none.
     */
    public static List<Integer> stupidImplementation(int transfer, List<Integer> payments)
    {
        Collection<List<Integer>> lists = Collections2.orderedPermutations(payments);
        
        for (List<Integer> l : lists)
        {
            int sum = 0;
            int index = 0;
            for (int i : l)
            {
                sum += i;
                index++;
                if (sum == transfer)
                {
                    return l.subList(0, index);
                }
                if (sum > transfer)
                {
                    continue;
                }
            }
        }
        
        return null;
    }
    
    public static void main(String[] args)
    throws IOException
    {
        DataSource source = new DataSource("./inputs/example.txt");
        source.readData();
        List<Integer> res = AccountingDilemma.solve(source.getBankTransfer(), source.getDuePayments());
        System.out.println();
        System.out.println(res);
    }
}
